// 替换字符串中的空格为 %20
// 1、最简单直接的办法就是从前往后遍历，遇到一个空格就替换一个
//    这样操作的话，每次替换的时候都要将这个空格后面的字符串全部向后移动两个位置
//    时间复杂度为O(n2)
// 2、优化后的方法
//    初始化一个新的空间保存替换空格之后的字符串，长度为原字符串长度加上空格个数乘以2
//    1、定义两个指针left和right，其中一个先遍历一遍，找到空格的个数
//    2、将旧字符串拷贝到新空间
//    3、right指向新空间的末尾的前一个(\0)，left指向旧字符串的最后一个字符
//    4、判断left是否指向空格
//    	否：*right = *left; --right, --left;
//    	是：(*right)-- = 0, (*rihgt)-- = 2, (*right)-- = %; --left
//    5、如果left == right 或者 left 已经指向了第一个字符就表示替换完成
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

char* Replace(char** str, int len)
{
	// 判空
	if(NULL == *str || len <= 0) {
		return NULL;
	}

	// 计算空格的个数
	char* left = *str;
	char* right = *str;
	int blank_num = 0;
	while(*left != '\0') {
		if(*left == ' ')
			++blank_num;
		++left;
	}
	int newLen = len + 2*blank_num + 1;

	char* strTemp = (char*)malloc(sizeof(char) * newLen);
	if(NULL == strTemp) {
		return NULL;
	}

	right = strTemp + newLen;
	*right-- = '\0';

	while(left >= (*str)) {
		if(*left == ' ') {
			*right-- = '0';
			*right-- = '2';
			*right-- = '%';
			left--;
		} else {
			*right = *left;
			right--;
			left--;
		}
	}

	return strTemp;
}

int main()
{
	char* str = "I am LuBenwei, I am scientist";
	int len = strlen(str);
	printf("Originaly String : %s\n", str);
	printf("    Newly String : %s\n", Replace(&str, len));

	return 0;
}
